Se ssh ci mette troppo a collegarsi al server e chiedervi la password, probabilmente è un problema di soluzione dei nomi. La soluzione è modificare il file /etc/nsswitch.conf sostituendo il parametro:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
con
hosts: files dns