I just upgraded from Natty to Oneiric, and things went really smoothly except that now when I ssh to a remote server it takes about 10 seconds to prompt for the password. I regularly remote to 4 servers (RedHat and HP-UX), and they're all just as slow.

When I run ssh -vvv user@host I get the following:
OpenSSH_5.8p1 Debian-7ubuntu1, OpenSSL 1.0.0e 6 Sep 2011
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug2: ssh_connect: needpriv 0
<10 second delay>
debug1: Connecting to remotehost [XXX.XXX.XXX.XXX] port 22.
debug1: Connection established.

I don't think this is an sshd configuration issue because our hosts haven't changed. It doesn't seem that the /etc/ssh/ssh_config changed either. The only lines uncommented in my ssh_config are the default SendEnv and HashKnownHosts settings (LANG LC_* and yes, respectively).

Any ideas on why this is slow all of a sudden?