slow ssh and ssl ... dns problem?

[Duane Winner]

Can anybody provide me with some insight into this before I rip all of 
my hair out:

Starting 3 days ago, suddenly it seemed to take a very, very, verly long 
time for ssh and ssl communications to negotiate between nodes on my 
network.

I have 3 subnets:

a LAN (10.10.0.0/16)
a DMZ (10.20.0.0/16)
a secured subnet for databases (10.30.0.0/16)

I have 2 DNS/Bind servers (9.3.1) running in the DMZ: 1 for the public 
web servers that get NAT'd, and provide public DNS lookups for the 
outside world. The other DNS server is for internal queries, providing 
the cooresponding private IP addresses to LAN clients and servers in the 
DMZ and secure subnet. Both sDNS servers are running FreeBSD (one is 
5.2.1, the other is 5.3)

Everything has been working great for months, until, like I said, 3 days 
ago. Some SSH negotiations were taking so long that they would time out 
before I would have a chance to enter the password for my private key. 
Apache/SSL communincations are also taking a long time. But when I make 
intial connections over port 80, it is very fast. I have also been able 
to make straight postgresql connections from nodes on my LAN to database 
servers in my secure subnet, but if I ssh to and from the same 
boxes....slow timeouts. It seems to be that encrypted traffic is having 
a problem.

The weird thing is that when I tried on a couple of servers to change 
the DNS server in resolv.conf from the internal (private IP address) DNS 
server to the public server, it seemed to speed things up. But I don't 
understand why....why would it be faster if a lookup reply is providing 
the external PUBLIC ip address instead of the internal PRIVATE ip 
address? And I also don't understand why this would have just suddenly 
started 3 days ago after working fine.

All the subnets are seperated by a Cisco PIX 515 firewall, and I see no 
errors on it. I also see no errors on any of my FreeBSD boxes in the 
logs (other than the SSH timeout errors). I've tried rebooting the PIX, 
rebooting my DNS servers, rebooting all the equipment on my 
communication rack (router, firewall, switches, etc.). I'm really confused.

One thing that has helped is that on 5.3 boxes, I put "UseDNS no" in 
sshd_config, and that seemed to help the SSH problem (but no 
Apache/SSL). I can't do this on all the boxes, though...some are 5.2.1, 
and when I put the same directive in there, I get an invalid config 
message when I try to restart SSH.

Thanks for any help on this. I am going insane.

P.S.: I cross-posted this to the freebsd-questions mailing list, and I 
did recieve a reply that others are having the same problem...and it all 
seemed to start about the same time as it did for me: around noon EST on 
Friday 5/3.

-DW