SSH Connections Slow to Connect

[Rhugga Harper]

I have a RH AS 3 U4 system. (Dell 2650, 2x3.00 Ghz, 6gb RAM). When I ssh to
several Solaris 8/9 systems from this box I get about a 5 second delay
before connecting, however, a solaris system on the same network as this AS3
box has less than a second connection overhead:
 Note: I am using trusted keys and ssh proto version 2.

<solaris9host>:~ #time ssh myserver1 uptime
12:15pm up 17 day(s), 7:10, 4 users, load average: 1.23, 1.29, 1.47

real 0m0.612s
user 0m0.150s
sys 0m0.020s

<redhatas3host>: time ssh myserver1 uptime
12:15pm up 17 day(s), 7:11, 4 users, load average: 1.25, 1.29, 1.46

real 0m6.675s
user 0m0.020s
sys 0m0.000s

It is not DNS related, DNS lookups are also subsecond, but to be sure I
configured the sshd daemon on all systems to not use DNS. I then made sure
all the host names are in each system's host file.

The ssh_config file on both client systems are identical. The sshd server
these clients are connecting to is this version: OpenSSH_3.8.1p1, OpenSSL
0.9.7d 17 Mar 2004

I remember this problem several years ago and can't remember the cause now.
Anyone have any ideas?

Here is the kernel version of the redhat client that is slow to connect:

Linux <redhatas3host> 2.4.21-27.0.2.1.7.ELhugemem #1 SMP Mon May 16 16:27:47
PDT 2005 i686 i686 i386 GNU/Linux

Thanks,

CC