delay after ssh'ing into a server

[Bill Tangren <bjt aa usno navy mil>]

I am having an odd problem with one of my RHEL servers. When I issue the command 
to ssh into it:

$ ssh aa

there is a 30 second delay before I get the password prompt. I tried deleting 
the appropriate line in ~/.ssh/known-hosts and trying it again, but I still got 
a 30 second delay before I got this message:

The authenticity of host 'aa (10.1.5.93)' can't be established.
RSA key fingerprint is <a:long:hex:number>.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'aa,10.1.5.93' (RSA) to the list of known hosts.

This is what the log looks like during this time:

Oct  5 14:52:30 aa xinetd[3098]: START: ssh pid=23524 from=10.1.5.58
Oct  5 18:53:12 aa sshd[23567]: Accepted password for bjt from 10.1.5.58 port 
32818 ssh2
Oct  5 14:53:12 aa sshd[23524]: Accepted password for bjt from 10.1.5.58 port 
32818 ssh2

Notice the 42 second time delay. The first line appeared in the log just after I 
send the "ssh aa" command.

I must have done something to make the system delay after receiving the 
connection request, but I can't imagine what. Googling turned up nothing for me.

Any ideas?

Bill Tangren