Comment 33 for bug 84899

Same problem, tried both fixes but neither resolved. My problem apparently was in the reverse dns. Adding entries for each system into /etc/hosts worked perfect. I reverted the change to /etc/ssh/ssh_config and reenabled mdns and the speed stayed fast. Check the basics first, this was my fix, your milage may vary.

127.0.0.1 localhost
10.0.0.13 lithium.domain.tld lithium
10.0.0.12 helium.domain.tld helium
10.0.0.13 hydrogen.domain.tld hydrogen

# The following lines are desirable for IPv6 capable hosts
::1 ip6-localhost ip6-loopback
fe00::0 ip6-localnet
ff00::0 ip6-mcastprefix
ff02::1 ip6-allnodes
ff02::2 ip6-allrouters
ff02::3 ip6-allhosts

** If you do not have a domain name you can use .local or just hostnames.