I have seen this when gssapi (?) was enabled and not used as well. At least I think it was called gssapi, it's been awhile. I disabled it and things went quickly again . However go for the low hanging fruit and make sure it's not a reverse dns issue first. :).