Entity Framework でストアド プロシージャが遅い

パラメータのスニッフィングが疑われます。

プロシージャにアンチパラメータ スニッフィング コードを適用してみてください。 (使用する前にローカル変数にパラメータを割り当てます)。

http://blogs .technet.com/b/mdegre/archive/2012/03/19/what-is-parameter-sniffing.aspx