SQL timeout from a simple, one table, query

My query is dead simple but sometimes it gets a timeout exception.

SELECT TOP 100 * 
FROM [cmn].[ProductChange] 
WHERE shop_id = @shopId 
ORDER BY changed_at DESC

This is the execution plan:

If I test the query in SSMS, the first time it is really slow, over 30 seconds, but the next times, it's much faster.

This is the primary key of the table:

ALTER TABLE [cmn].[ProductChange] 
ADD CONSTRAINT [PK_cmn_ProductChange] 
PRIMARY KEY CLUSTERED ([product_id] ASC)
WITH (STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, 
    ONLINE = OFF, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]

I have about 350k rows which I don't think that are that much. Are they?

I have only one FK with the Shop, the PK is an external ID and it's not connected to any other table.

My columns are:

product_Id PK, BigInt
shop_id FK, BigInt
column1 nvarchar(800)
column2 nvarchar(max)
column_3 smallint
changed_at datetime2(7)
column_4 datetime2(7)
column_5 datetime2(7)

How can I make this query much faster?

The reason your query is slow is almost certainly because it has to read the all matching shop_id rows, do Key Lookups for all of them, and then sort to get those 100 rows. On subsequent runs all that data is in the cache so it's faster.

Looks like you need the following index to support your query

CREATE NONCLUSTERED INDEX IX_changed_at ON cmn.ProductChange
  (shop_id ASC, changed_at DESC);

Ideally you would have INCLUDE columns on that index for all your SELECT columns, but I don't know what this SELECT * involves. You should really only specify the exact columns you need, and only put those into the INCLUDE.