We encountered the same issue.
Jenkins version: 2.164.1
Git plugin version: 3.9.1
Git Parameter plugin version: 0.9.6
Master OS: Ubuntu 16.04.2
Master JVM version: 1.8.0_191
Master remoting version: 3.29
Slave OS: Windows 10 Pro 10.0.17763
Slave JVM version: 1.8.0_201
Slave remoting version: 3.29
Running `println "git ls-remote -h <URL>".execute().text` in the script console of the slave works fine, while clicking on the job's "Build with Parameters" (which runs the exact same command) brings out the same output as that of the OP: "stderr: /tmp/ssh5441311447548085150.sh: 6: /tmp/ssh5441311447548085150.sh: ssh: not found".
The "ls-remote" during "Build with Parameters" only works while the slave is offline. The last successful build executed "ls-remote" on the master. This confirms the OP's hypothesis.
Partial workaround: setting "Force polling using workspace" under "Additional Behaviours" in "Source Code Management" with "Git", and then duplicating the job. This workaround only helps for the first build. After the first one, the issue reproduces.
According to this, an update to the latest version of the Git Parameter plugin may solve this issue, but by looking at the OP's error reporting output, it's already the latest version there.