OFFSET-FETCH is slow - how to optimize

Question

I am using the following query to implement server-side pagination (10000 and 1000 are parameters in my query):

SELECT Name, Id, Color
FROM MyTable
WHERE Color = 'red'
ORDER BY Id,Name DESC
OFFSET 10000 ROWS 
FETCH NEXT 1000 ROWS ONLY

However, this query takes over 4 minutes if select/from/where results in about a million records.

I have an index on both Id and Name column.

I was wondering how this can be furthered optimized.

Answer 1

Answering my own question.

There were some nice suggestions in the comments, but the winner (by a considerable margin) was to add the following index suggested by @DanGuzman:

CREATE unique nonclustered index idx_MyTable_Color_Id_Name ON dbo.MyTable(Color, Id, Name DESC);