I have the same issue with one of the jobs on my Jenkins installation.
Error Output from the Console Log
> git fetch --tags --progress git@git-server:organization/project.git +refs/heads/:refs/remotes/origin/
ERROR: Error cloning remote repo 'origin'
hudson.plugins.git.GitException: Command "git fetch --tags --progress git@git-server:organization/project.git +refs/heads/:refs/remotes/origin/" returned status code 128:
stderr: /home/jenkins/workspace/project-name@tmp/ssh8085679836267327653.sh: 6: /home/jenkins/workspace/project-name@tmp/ssh8085679836267327653.sh: ssh: not found
fatal: Could not read from remote repository.
Please make sure you have the correct access rights
and the repository exists.
Much like John Elion above, when I make a clone of the affected job, the cloned job has the same issue as the original job. If I create an entirely new job, and fill in the configuration values manually, the new job works fine. Somehow, the cloned job is "inheriting" the buggy behavior from its parent.
My jobs are the FreeStyle type, and they use the Build Parameters configuration option. On my Jenkins installation, I use the Git plug-in, the Git Client plug-in, and the GitLab plug-in. The Jenkins master and all of the Jenkins slaves run Ubuntu Linux.
So far, the only solution to this issue I can find is to manually re-create the affected job (no cloning).
Jenkins Master: Ubuntu 16.04.5
Jenkins Slaves: Ubuntu 16.04.5
Git Plug-in: 3.9.3
Git Client Plug-in: 2.7.7
GitLab Plug-in: 1.5.12