Se ti capita di avere un pc linux che impiega molto tempo a collegarsi ad un server via ssh, il problema potrebbe non essere la connessione lenta, ma un problema di configurazione lato client o lato server.

Lato client: prova a controllare un parametro nel file di configurazione /etc/ssh/ssh_config :

GSSAPIAuthentication no

Impostando questo parametro a no, la connessione "magicamente" andrà più veloce...
Lato server: prova a controllare un parametro nel file di configurazione /etc/ssh/sshd_config :

#UseDNS yes

modificalo in

UseDNS no

Riavvia il servizio e dovresti andare più veloce...