Isso soa como se fosse o mesmo problema que eu experimentei. Para mim, toda vez que alguém tenta fazer login através do SSH, o daemon do SSH tenta realizar uma pesquisa inversa. Em algumas redes isso causa problemas, e o usuário tem que esperar até que a pesquisa de DNS expire antes que ele possa continuar.
Adicione a seguinte linha a /etc/ssh/sshd_config
e veja se isso ajuda;
UseDNS no
Não se esqueça de reiniciar o daemon SSH;
service ssh restart