Prepared statements with many parameters is slow
1) IN clauses are during the optimization phase expanded to multiple OR. Example: C1 = @P1 Or C1 = @P2.

2) If the parameter count is greater than 63 the optimization process will build an internal table for it. Having said that, I’m not so sure about the stats being generated on the dynamically generated temp table.

3) Putting your parameters in a #temp table may result in a slightly different execution plan, however, this may also introduce concurrency issues depending on the design of your application.

4) I would, before introducing a temp table, try to rewrite the query into smaller logical chunks. For example, isolate the filter process against an optimized smaller outer table and cross apply that with the inner table. 

5) Ensure that your stats are updated and that you are getting a parallel execution plan. Would be nice if you could share your plan so we can have a peek at what’s going on.


  Blockquote
  The estimated execution plan shows that 100% of time is spent on an "index seek, non-clustered". From this I deduce that the situation can not be improved using indexes, 


6) "index seek" can be "bad" if they represent a lot of logical reads. You should check the statistics in order to be sure that index tuning won't yield any better results.