Como indicado nos comentários, isso provavelmente está sendo causado pela configuração UseDNS yes
no sshd_config
no servidor.
A configuração UseDNS
é um culpado comum para esse problema. Basicamente, o que acontece é que o seu netblock IP tem um servidor DNS defeituoso ou ausente. Então, o sshd está tentando fazer uma pesquisa reversa no seu endereço IP e aguarda até expirar. Outras pessoas não experimentam o atraso, pois têm um servidor DNS funcional para o seu netblock.
A maioria das pessoas rejeita essa configuração por essa mesma razão. Embora sim, a configuração está lá por segurança, é praticamente inútil .
A solução é simplesmente definir o seguinte no sshd_config
:
UseDNS no