Debian Configuration :: OpenSSH - Sshd Returns Login Prompt With Delay

On a Debian 5.0.8 I have a problem with OpenSSH server (sshd): when connecting to it from another host there is always a 10 seconds delay before sshd gives login prompt to the client. After the connection is established the communication goes on without any interruption. This long delay started to happen a few months ago and sshd_config was not changed at that time.

Here is a short description of the conversation between the putty client (on MS Windows) and sshd:
- putty client starts connection to sshd
- 10 s delay
- sshd returns "login as:"
- user types username in putty window
- sshd returns "password:"
- user types password in putty window
- sshd returns MotD and shell prompt

Here is a short description of the conversation between the OpenSSH client (on a Debian 6) and sshd:
- client does "ssh user@host.foo.bar"
- 10 s delay
- sshd returns "Password:"
- user types password
- sshd returns MotD and shell prompt

I tried connecting from:
- local host - NO DELAY
- a host on the same subnet - delay exists
- a host on another subnet - delay exists

I've found the following suggestions but to no avail (of course I restarted sshd after changing its configuration):
- on server put "UseDNS no" at the end of /etc/ssh/sshd_config
- in /etc/hosts on the server define mappings between IP addresses and host names for the ssh clients
- on client use "GSSAPIAuthentication no" in /etc/ssh/ssh_config

Here are some logs and configurations: