I am under a proxy and I am pushing in to git successfully for quite a while.
Now I am not able to push into git all of a sudden.
I have set the RSA key and the proxy and double checked them, with no avail and git is throwing me the error shown in the title of the page.

For my case none of the suggested solutions worked so I tried to fix it myself and I got it resolved.

For me I am getting this error on my AWS EC2 UBUNTU instance, what I did to resolve it was to edit the ssh config (or add it if it does not exist).

sudo nano ~/.ssh/config

And I added the following

Host github.com
 Hostname ssh.github.com
 Port 443

Then, run the command ssh -T [email protected] to confirm if the issue is fixed.

According to this

Sometimes, firewalls refuse to allow SSH connections entirely. If using HTTPS cloning with credential caching is not an option, you can attempt to clone using an SSH connection made over the HTTPS port. Most firewall rules should allow this, but proxy servers may interfere

Hopefully this helps anyone else who's having the same issue I did.