Git server's host key not cached in registry - GitHub.com

Using git-for-windows with GIT_SSH pointing to plink.exe, opening a putty to the server and accepting the host key (and then killing the putty session, not even proceeding with logging in) was enough to solve this issue for me.

On Windows, it seems that sometimes you don't get to actually accept a server's host key.

Try one of the following commands from the Power Shell:

ssh github.com

Or

plink.exe -agent github.com

Run these standalone and press y when asked to accept the host key.

Use ssh-add to add your private key to the current Power Shell session:

C:> ssh-add PATH\TO\PRIVATE\KEY

Afterwards, you should be able to successfully run git push.

Source: http://help.github.com/ssh-issues/

The ideal solution would be (if you really don't need to use plink in git) removing the GIT_SSH environment variable and generating a new keypair with command ssh-keygen -t rsa -C "youremail" on Git Bash then change your ssh key in github because from what I've understood from the comments is putty and openssh is conflicting.

However, if you still want to use plink you can use PuTTYgen to generate a PuTTY format key then change your public key in github and load your private key in PuTTYagent then you should do a connect to github.com with PuTTY this would add githubs fingerprint to known_hosts and you are good to go. This would be a resource to github with PuTTY http://nathanj.github.com/gitguide/tour.html