Comment 7 for bug 1270445

This must be related or same (older) bug: https://bugs.launchpad.net/ubuntu/+source/openssh/+bug/84899

"Gabriel de Perthuis (g2p) wrote on 2012-10-24: #70

So here's a list of the workarounds:

On the client:
# disable reverse lookups in kerberos
echo $'[libdefaults]\n\trdns=false' |sudo tee -a /etc/krb5.conf
# Alternatively, remove mdns, mdns4, mdns6 from nsswitch
/etc/nsswitch.conf
# Or disable GSSAPIAuthentication in ~/.ssh/config or /etc/ssh/ssh_config or with the -o flag
GSSAPIAuthentication=no

On the server:
GSSAPIAuthentication=no in /etc/ssh/sshd_config

Fixes that require coding would be the one at http://bugs.debian.org/409360#40 which seems simple enough.
Paliatives would be a cache of notfound results in avahi or in sshd (so that the 5 seconds Avahi timeout isn't repeated for the four times ssh tries name resolution)."