Получите SQL, выполняемый с помощью инструмента профилирования (у SSMS есть один, или Express Profiler), затем запустите его в рамках плана выполнения SSMS / w. Это может выделить улучшение индексации. Если время выполнения в SSMS примерно соответствует тому, что вы видите в EF, то единственным реальным способом улучшения будет аппаратное обеспечение на коробке SQL. Вы выполняете запрос, который будет касаться 5-метровых строк, как бы вы на них ни смотрели.
Подобные операции не являются чем-то необычным, просто пользователь не может ожидать и ждать. Это скорее запрос типа отчета, поэтому, когда я сталкиваюсь с подобными требованиями, я бы посмотрел варианты, когда пользователи ставят в очередь запрос, где они могут получить уведомление, когда операция завершается для получения результатов. Это должно быть настроено для предотвращения повторного запроса пользователями обновлений (типа «не уверен, если я нажал») или для предотвращения одновременного запуска слишком большого количества запросов от нескольких пользователей. В идеале это было бы кандидатом на запуск реплики отчетов только для чтения, а не на производственную базу данных чтения-записи, чтобы избежать замедления блокировок / вмешательства в регулярные операции.