SSH connection to OpenBSD UNIX

When I try to connect to OpenBSD UNIX box via SSH port 22 it takes really long time to connect. On the actual console I see the following messages:
sshd[4753]: log: connection from xxx.xxx.xxx.xxx port nnn
sshd[4753]: log: could not reverse map address xxx.xxx.xxx.xxx
Where xxx.xxx.xxx.xxx is the address of the client I am trying to connect from.
I tried pinging my DNS server – unsuccessful.
But I could ping other IPs on my network and I could ping the DNS server from any other machine.