Nós sofremos o mesmo problema exato e a causa foi um erro de configuração da MTU, mas há muitas outras causas possíveis.
A chave era farejar o tráfego em nosso roteador de borda, onde vimos mensagens ICMP para o servidor (GitHub.com) pedindo fragmentação . Isso estava bagunçando a conexão, com retransmissões, ACKs duplicados e assim.
OpacoteICMPtinhaumcampo,MTUofnexthop
comumvalorestranho,1450.Ovalorusualé1500.
Verificamos nosso roteador e uma das interfaces (um túnel Ethernet) tinha esse valor como MTU, então o roteador estava tomando o MTU mínimo de todas as interfaces como próximo salto. Assim que removemos essa interface (não foi usada), o handshake do SSH começou a funcionar novamente.