look at the execution plan to find clues

Replace the * with the actual column names - don't know why, but it sometimes helps

add index to each column and try (until you find the best one)

try to change the primary key's index type - try Clustered instead of Non-Clustered

try to create a view upon this table and query from the view instead