Something must have changed. Issues are just the results of one or more causes
Well, for starters, can you delete the private key and generate new public/private key and check? (to be honest if there was key mismatch, it would prompt you for password; should not hang)
Also, check if DNS is enabled in the remote machines's ssh config. If so, is you DNS server responding to the queries properly?
Does it happen while connecting from a particular server?