matt-walston (#33) solution worked for me. I'm on Ubuntu 12.04.3 connecting to RedHat ssh server.
"My problem apparently was in the reverse dns. Adding entries for each system into /etc/hosts worked perfect." -- You received this bug notification because you are a member of Ubuntu Bugs, which is subscribed to Ubuntu. https://bugs.launchpad.net/bugs/84899 Title: SSH with GSSAPIAuthentication option on SSH servers are very slow To manage notifications about this bug go to: https://bugs.launchpad.net/openssh/+bug/84899/+subscriptions -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs