Jenkins master 2.60.1-rc1 (and versions 2.58 through 2.64) fail to connect to agents with "Manually provided key Verification Strategy".

Jenkins 2.46.3 (and versions through 2.57) are able to connect to agents when the host key of the agent is entered in the agent definition as a "Manually provided key Verification Strategy".  Upgrading to Jenkins 2.58 or later (including 2.60.1-rc1) will prevent those agents from connecting.

One work around is to switch the key verification strategy from "Manually provided key Verification Strategy" to "Non-verifying Verification Strategy".

Steps I took to confirm the problem:

1. Install and configure an Ubuntu 16.04 operating system for Jenkins 2.46.3
   1. Install the base operating system
   2. Install JDK 8 and git
   3. Add Jenkins LTS apt repository per the Jenkins Ubuntu install instructions
2. Create a new user "agent-a" on that Ubuntu 16.04 machine
   1. Create the user with adduser
   2. Login as the user and create an ssh key with ssh-keygen
   3. Copy .ssh/id_rsa.pub to .ssh/authorized_keys so that agent-a's private key can be used for login as agent-a
3. Configure Jenkins 2.46.3 to run an agent on that machine as user agent-a
   1. Add agent-a private key as a credential
   2. Use agent-a private key credential to configure the ssh slave
   3. Extract the rsa host key from the machine with ssh-keyscan localhost and add that host key as the host key to be used in the "Manually provided key Verification Strategy"
4. Install and configure another Ubuntu 16.04 machine for agent-b
   1. Install the base operating system
   2. Install JDK 8 and git
   3. Create user agent-b on this machine with ssh key and authorized keys similar to configuration on master
5. Configure Jenkins 2.46.3 to run an agent as user agent-b on the second machine
   1. Add agent-b private key as a credential
   2. Use agent-b private key credential to configure the ssh slave
   3. Extract the rsa host key from the machine with ssh-keyscan localhost and add that host key as the host key to be used in the "Manually provided key Verification Strategy"
6. Install and configure a Debian 8 machine for agent-c
   1. Install the operating system
   2. Add JDK 8 from jessie-backports (see stackoverflow for technique)
   3. Add git
   4. Create agent-c user with adduser, with private key as in the preceding two machines
7. Configure Jenkins 2.46.3 to run an agent as agent-c on the third machine
   1. Add agent-c private key as a credential
   2. Use agent-c private key credential to configure the ssh slave
   3. Extract the rsa host key from the machine with ssh-keyscan localhost and add that host key as the host key to be used in the "Manually provided key Verification Strategy"
8. Confirm all agents are responding and system information is as expected
9. Stop Jenkins on the master with /etc/init.d/jenkins stop
10. Replace /usr/share/jenkins/jenkins.war with the jenkins 2.60.1-rc1 file
11. Start Jenkins on the master with /etc/init.d/jenkins start

Once Jenkins 2.60.1-rc1 starts, you'll see that the agents will not start, and the agent log will report that host key verification failed.

I can provide credentials to those test machines if they can help with the diagnosis.

The problem shows itself even on the Ubuntu machine using an agent hosted on its own machine.  The other machines are just extra evidence that the problem is real.  I've seen the same behavior on CentOS 7 agents also.

Agent log for the agent on the same machine is below:
 

[06/09/17 23:58:11] [SSH] Opening SSH connection to 54.89.141.156:22.
[06/09/17 23:58:11] [SSH] WARNING: The SSH key for this host does not match the key required in the connection configuration. Connections will be denied until until the host key matches the configuration key.
Key exchange was not finished, connection is closed.
java.io.IOException: There was a problem while connecting to 54.89.141.156:22
	at com.trilead.ssh2.Connection.connect(Connection.java:834)
	at com.trilead.ssh2.Connection.connect(Connection.java:703)
	at com.trilead.ssh2.Connection.connect(Connection.java:617)
	at hudson.plugins.sshslaves.SSHLauncher.openConnection(SSHLauncher.java:1265)
	at hudson.plugins.sshslaves.SSHLauncher$2.call(SSHLauncher.java:790)
	at hudson.plugins.sshslaves.SSHLauncher$2.call(SSHLauncher.java:785)
	at java.util.concurrent.FutureTask.run(FutureTask.java:266)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
	at java.lang.Thread.run(Thread.java:748)
Caused by: java.io.IOException: Key exchange was not finished, connection is closed.
	at com.trilead.ssh2.transport.KexManager.getOrWaitForConnectionInfo(KexManager.java:95)
	at com.trilead.ssh2.transport.TransportManager.getConnectionInfo(TransportManager.java:237)
	at com.trilead.ssh2.Connection.connect(Connection.java:786)
	... 9 more
Caused by: java.io.IOException: The server hostkey was not accepted by the verifier callback
	at com.trilead.ssh2.transport.KexManager.handleMessage(KexManager.java:548)
	at com.trilead.ssh2.transport.TransportManager.receiveLoop(TransportManager.java:790)
	at com.trilead.ssh2.transport.TransportManager$1.run(TransportManager.java:502)
	... 1 more
[06/09/17 23:58:11] Launch failed - cleaning up connection
[06/09/17 23:58:11] [SSH] Connection closed.