Minha expectativa seria uma das seguintes:
- Muitos dados estão sendo retornados e demoramos muito para que os dados cruzem o fio.
- Problema de desempenho com a máquina remota.
Clique no botão da barra de ferramentas na janela de consulta "Incluir estatísticas do cliente" e observe o que é retornado após a execução da consulta. Você pode ver quantos bytes foram recebidos do servidor, tempo de execução, etc.
Client Execution Time 12:08:38
Query Profile Statistics
Number of INSERT, DELETE and UPDATE statements 0
Rows affected by INSERT, DELETE, or UPDATE statements 0
Number of SELECT statements 3
Rows returned by SELECT statements 15
Number of transactions 0
Network Statistics
Number of server roundtrips 3
TDS packets sent from client 3
TDS packets received from server 7
Bytes sent from client 240
Bytes received from server 21306
Time Statistics
Client processing time 31
Total execution time 61093
Wait time on server replies 61062
Editar:
Seu comentário diz que está retornando apenas 39 linhas, portanto, provavelmente não é uma transferência de dados entre o cliente e o servidor.
Eu consideraria a execução do SQL Profiler no servidor filtrado para o seu cliente e ver o que poderia estar acontecendo. Aqui estão alguns bons artigos sobre o uso do SQL Profiler: