Thanks for the additional information. It hints at several different areas which might be problems. Unfortunately, none of them seem likely (to me) to actually address the error message that is being reported.
JENKINS-20879 reports that passphrase protected ssh keys don't work on Windows. There is a comment in that bug report which hints they might have worked at one time, but I spent several hours trying to find a way to make them work on Windows without success. My suspicion is that they never worked on Windows. There are even cases still today where they do not work on Linux.
JENKINS-30755 reports that the GIT_HOME variable is not used in the git source code or in the git client plugin source code or in the git plugin source code. I don't think it will harm your installation, but as far as I can tell, it is unnecessary.
JENKINS-20356 reports that a windows slave (or master) running as a service can't clone using an ssh private key. If Jenkins is running as a Windows service, I have little hope for you to be able to use ssh protected credentials.
JENKINS-24368 and JENKINS-26757 report two different authentication problems that seem to be specific to bitbucket repositories.
JENKINS-30045 reports a case where two users have a git 2.5.0 (and 2.6.0) installation on Windows that can't find ssh.exe. I haven't found (yet) what is different about their installation compared to the many installations I'm using of git 2.5.0 and git 2.6.0 for Windows, but they clearly have seen a problem.
Have you attempted removing the Tortoise Git entries from your PATH, in case programs in those directories are returning different results than programs in the git distribution?
Have you attempted to remove the GIT_SSH environment variable and instead allow the plugin to manage the value of GIT_SSH? There is code in the plugin that attempts several ways of guessing the correct value to assign to GIT_SSH.
Are you using a Jenkins credential to define the credentials, or only relying on the private key stored in %USERPROFILE%\.ssh\id_rsa? The plugin has worked well for me using the Jenkins credentials system. I don't test with credentials stored locally in %USERPROFILE%\.ssh\id_rsa.
Are you certain that the git program is really in C:\Progra~1\Git\bin\git.exe, or is it in C:\Progra~2\Git\bin\git.exe (or some other differently named location)? For example, if you run a command prompt build step in a job which has no scm, can that command prompt build step execute the command "C:\Progra~1\Git\bin\git.exe"? Can it execute the command C:/Progra~1/Git/bin/git.exe?
Have you tried specifying the location of the git executable with the spaces in the path to git, as in "C:\Program Files\Git\bin\git.exe"? That is the technique I use on most of my test and production machines and it works quite well.
Is there a reason you feel you need to use the mangled form of the path rather than the form which includes spaces?