recently i prepared RHEL AS4.8 server connected behind firewall, in DMZ.
the domain part of hostname of the server was reflecting the internet domain name and the local MS-AD Domain was <domain>.local
connecting to this nix box from ms-platform was taking pretty long time to login after username & password request.
Upon googling i found this link which solved my problem.
Add the following to /etc/ssh/sshd_config on your SSH server
Then restart the ssh daemon and your pauses should be gone.