Try to change this in your /etc/ssh/sshd_config:
If in CentOS 5, change:
AddressFamily any to: AddressFamily inet
If in CentOS 4, change:
ListenAddress :: to: ListenAddress <ip_address_of_your_server_here>
Uncomment those lines if needed.
Change:
GSSAPIAuthentication yes to: GSSAPIAuthentication no
Change:
UseDNS yes to: UseDNS no
Uncomment the last line if applicable.
Then restart your sshd and try to connect again, see if that improved the situation or not. If it did, it's related to DNS.
Keep a backup of your original file and restore it later. Better yet, do the changes on a copied file and then start sshd in the command line in debugging mode with the -f option to specify the new config file.
HTH, Filipe