Dies ist mir bei einigen lang laufenden Skripten passiert, die neue Indizes generiert haben. Die Problemumgehung, die wir verwendet haben, war die Verwendung von:
update-database -Script
EF spuckt dann die SQL-Migration auf den Bildschirm aus und wir konnten die SQL direkt vom Server ausführen, sodass es keine Timeout-Probleme gab.