I confirm this problem in Ubuntu 10.10. I experienced the exact symptoms as described in https://bugs.launchpad.net/ubuntu/+source/openssh/+bug/416264, but I think the bug belongs to #84899.
Ubuntu uses the Debian package, as shown at the top of the attached file (personal information removed):
OpenSSH_5.5p1 Debian-4ubuntu4, OpenSSL 0.9.8o 01 Jun 2010
The remote server is running Red Hat, which has /etc/ssh/ssh_config with: GSSAPIAuthentication Yes
I have no access to modify the remote server's files. So, I think the problem is bigger than just Debian.
I created a user ~/.ssh/config file to contain:
The work-around fixes the problem, access is very fast.
("cat /proc/version" will display the distro name, "uname -a" does not display the distro name.)