I had slow login problems with my SSH server for many months, and never bothered to try and fix it. Finally I got sick of it, and enabled verbose mode. I noticed it was doing public key authentication, GSSAPI authentication, and then password. The authentication would fail on public key, then the GSSAPI authentication would sit there for a long time, before moving on to password authentication.
Add the following to your /etc/ssh/sshd_config
GSSAPIAuthentication no GSSAPICleanupCredentials no