Try setting UseDNS to "no" in your sshd_config and ssh_config. Also set GSSAPIAuthentication to no.


Which step is slow? The GSS authentication? You can give us timestamps by installing moreutils and running

ssh -vvv user@host 2> >(ts)

You can skip GSSAPI with this flag:

-o PreferredAuthentications=hostbased,publickey,keyboard-interactive,password