In aktuellen Versionen dauert der Start von ausgehenden ssh-Verbindungen mit Ubuntu (konkret 12.04) eine kleine Ewigkeit. Grund ist, das in der Konfiguration des ssh-clients (zu finden in /etc/ssh/ssh_config) folgende Zeilen am Ende stehen:
GSSAPIAuthentication yes GSSAPIDelegateCredentials no
Die erste der beiden beiden Zeilen sollte auskommentiert werden, damit der Client beim Verbindungsaufbau nicht auf das Angebot einer GSSAPI-Authentifizierung wartet. Die Zeile auszukommentieren ...
#GSSAPIAuthentication yes
... genügt also, denn der Default-Wert ist 'no'.
Natürlich kann man auch mit
GSSAPIAuthentication no
die GSSAPI-Authentifizierung explizit abschalten. Mit ssh -vvv kann man seinem Client übrigens beim Verbindungsaufbau zusehen und auf diese Weise leicht feststellen was da so lange dauert.