Jenkins: unable to connect to bitbucket git repository

Question

I'm trying to connect jenkins to a bitbucket git repository.

When I specify the repository URL in jenkins, it returns the following error message:

Failed to connect to repository : 
Command "git ls-remote -h <SSH_Git_url> HEAD" returned status code 128: stdout: stderr: Host key verification failed. 
fatal: Could not read from remote repository. Please make sure you have the correct access rights and the repository exists.

I have successfully run the above command(where jenkins is running) using Git Bash and the known_hosts file has the correct host address along with the port.

I have also used the set git_ssh_command="ssh -i <ActualPathToPrivateKey>" before running the above command, to check if that helps.

Some other points(not sure if these add to the question but trying to provide as much information as possible):

a. The public\private keys were created using the `ssh-keygen` command in the c:\users\<UserName>\.ssh folder. 
b. The public key was copied and added as a read\write access key for the repository in bitbucket.
c. Jenkins runs as a windows service and logs on as a "Local service account".

What could I be doing wrong?

Update: 12/11/2018:

The git version is 2.17.1.windows.2.

I tried the options suggested by @VonC and I get the same error as below. In the configure individual job=> credentials dropdown nothing shows.

Answer 1

Jenkins runs as a windows service and logs on as a "Local servvice account"

That means it might not have access the same environment variables as your account when you did your tests.
Make sure to register your ssh key in the SSH Credentials plugin.

And check your Git version: if 2.19.2, the ssh-keygen command has changed the generated key format (from PEM to openssh): see "Jenkins: what is the correct format for private key in Credentials".