Slow connect on ssh on Ubuntu
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