sshd tries reverse DNS lookups with UseDNS no

Nowadays the most frequent culprit is GSSAPI:

/etc/ssh/sshd_config:
GSSAPIAuthentication no

The other three culprits for Linux platform have been mentioned in other answer:

  • add to sshd a command line option -u0
  • set UseDNS no
  • don't use from=hostname inside authorized_keys files

Use DNS = no does not prevent sshd from performing DNS lookups, it prevents it from rejecting clients when PTR records don't match.

-u0 prevents sshd from logging DNS names in the utmp struct.

lookups might still happen depending one what a user has in their authorized_keys.

See this for a decent explanation:

http://lists.freebsd.org/pipermail/freebsd-stable/2006-November/030886.html