How to speed up a sample with pagination?

I must say, I'm not strong nuances, know sql in General.
Now the pagination is done via standard remembering the last ID. Something like this:

SELECT * FROM recording WHERE recording.id > 0 AND recording.artist_id = '269608' ORDER BY recording.id LIMIT 10

The request is 5-10 seconds. The query plan here https://explain.depesz.com/s/a8Xl
As you can see most of the time pulls the index scan, I do not understand why.
If you remove the ORDER BY it all the more fun https://explain.depesz.com/s/WpTp
Have noticed that if aydishnik artist not 269608 and less, for example 500, the query is very fast. And the more aydishnik, the longer the query is executed. Is this normal? The impression is that all the ID are converted in order until you reach the desired.
In General, as to be without ORDER BY, if needed and speed (primarily) and data filtering?
The table contains 18mn records, but I don't think it's just still daunting schema for DBMS (?)

UPD
Describe the task completely.
Need to get the tracks on aydishnik artist. The tracks are in the table recording artists in the artist table. But the tables are not related directly, but only through the other two artist_credit_name and artist_credit.
The connection next: artist.id <--> artist_credit_name .artist, artist_credit_name .artist_credit <--> artist_credit.id <--> recording.artist_credit
The whole scheme here
The full query looks like this:

SELECT recording.id AS "recordingId", recording.name AS, "trackName", "artist".name AS "artistName" FROM artist INNER JOIN artist_credit_name ON artist.id = artist_credit_name.artist INNER JOIN artist_credit_name artist_credit ON.artist_credit = artist_credit.id INNER JOIN recording ON artist_credit.id = recording.artist_credit WHERE artist.id = $(artistId) AND recording.id > $(index) ORDER BY recording.id LIMIT $(limit)

It turns out that one `artist.id` can have multiple `artist_credit.id`. So I tried to rewrite the query so that first select all `artist_credit.id` for a given artist and then them using the `WHERE IN` select tracks, acceleration is about 30% (although it may be error), but the result is still not the need.
Indexes on tables :
recording: id (PK),
artist_credit: id (PK),
artist_credit_name: id (PK), artist(FK),
artist: id (PK)
Can add an index on the field `recording.artist_credit` ? Don't know if you can add indexes on foreign keys?

UPD#2 Added index on `recording.artist_credit`, now the query goes fast