Este é um sintoma que tenho visto em intervalos regulares, e aposto que isso é causado por um dos saltos entre o servidor em nuvem e a rede do usuário, filtrando mensagens ICMP indiscriminadamente, causando falha na descoberta da MTU do caminho; a troca de chaves é a primeira parte do protocolo SSH, na qual é provável que grandes segmentos TCP sejam enviados pelo soquete e, muito provavelmente, acione o problema.
Duas maneiras fáceis de isolar o problema: tente fazer grandes trocas sobre algum outro protocolo entre os mesmos hosts (por exemplo, fazer upload de algum arquivo em um formulário da web) ou forçar artificialmente o MTU no host do usuário para algum valor pequeno o suficiente para se adaptar a qualquer MTU plausível ao longo da rede (~ 300b). Se o problema aparecer durante outras grandes transferências e desaparecer com o menor MTU, você encontrou o culpado.
(O motivo é que quando um pacote IP que tem o conjunto de sinalizadores DF (não fragmentado) é transmitido e não passa por um salto, o salto responderá com uma mensagem ICMP e filtrará essas mensagens ICMP out é uma configuração incorreta comum por administradores de redes inexperientes ou excessivamente paranóicos - assim, o host remetente nunca sabe o caminho. O MTU é menor do que ele pensa e os pacotes simplesmente desaparecem no éter).
A má notícia é que isso não é algo que pode ser corrigido em qualquer ponto de extremidade em geral, mas no salto onde a filtragem imprópria está ocorrendo. Você pode contornar o problema com MTUs configuradas manualmente, mas isso é um hack feio e é quebradiço na melhor das hipóteses.