Comment 70 for bug 84899

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).