This is a function inside the paramiko source code that does not (at least obviously does not) do anything like DNS lookups.
I’m at a bit of a loss, perhaps you can debug further?
Fedora 20 has a new enough SSH so the default connection type is “ssh” not paramiko there, curious if you have the same with “-c paramiko” on that box (and using the same key?)
So the reason is that my known_hosts file has over 5k records.
I think that Paramiko is for looping for each host in known_hosts and /etc/hosts file.
In my case it’s around 800k checks.