When trying to clone any Git repository with Jenkins 2.58, we ran into the following error:

Building in workspace /var/lib/jenkins/jobs/some-project/workspace
Fetching changes from the remote Git repository
ERROR: Error fetching remote repo 'origin'
hudson.plugins.git.GitException: Failed to fetch from git@our-git-server.local:some-namespace/some-project.git
    at hudson.plugins.git.GitSCM.fetchFrom(GitSCM.java:809)
    at hudson.plugins.git.GitSCM.retrieveChanges(GitSCM.java:1076)
    at hudson.plugins.git.GitSCM.checkout(GitSCM.java:1107)
    at hudson.scm.SCM.checkout(SCM.java:495)
    at hudson.model.AbstractProject.checkout(AbstractProject.java:1281)
    at hudson.model.AbstractBuild$AbstractBuildExecution.defaultCheckout(AbstractBuild.java:604)
    at jenkins.scm.SCMCheckoutStrategy.checkout(SCMCheckoutStrategy.java:86)
    at hudson.model.AbstractBuild$AbstractBuildExecution.run(AbstractBuild.java:529)
    at hudson.model.Run.execute(Run.java:1735)
    at hudson.model.FreeStyleBuild.run(FreeStyleBuild.java:43)
    at hudson.model.ResourceController.execute(ResourceController.java:97)
    at hudson.model.Executor.run(Executor.java:405)
Caused by: hudson.plugins.git.GitException: org.eclipse.jgit.api.errors.TransportException: git@our-git-server.local:some-namespace/some-project.git: Failed to connect
    at org.jenkinsci.plugins.gitclient.JGitAPIImpl$2.execute(JGitAPIImpl.java:619)
    at hudson.plugins.git.GitSCM.fetchFrom(GitSCM.java:807)
    ... 11 more
Caused by: org.eclipse.jgit.api.errors.TransportException: git@our-git-server.local:some-namespace/some-project.git: Failed to connect
    at org.eclipse.jgit.api.FetchCommand.call(FetchCommand.java:135)
    at org.jenkinsci.plugins.gitclient.JGitAPIImpl$2.execute(JGitAPIImpl.java:617)
    ... 12 more
Caused by: org.eclipse.jgit.errors.TransportException: git@our-git-server.local:some-namespace/some-project.git: Failed to connect
    at org.jenkinsci.plugins.gitclient.trilead.TrileadSessionFactory.getSession(TrileadSessionFactory.java:52)
    at org.eclipse.jgit.transport.SshTransport.getSession(SshTransport.java:137)
    at org.eclipse.jgit.transport.TransportGitSsh$SshFetchConnection.<init>(TransportGitSsh.java:264)
    at org.eclipse.jgit.transport.TransportGitSsh.openFetch(TransportGitSsh.java:162)
    at org.eclipse.jgit.transport.FetchProcess.executeImp(FetchProcess.java:136)
    at org.eclipse.jgit.transport.FetchProcess.execute(FetchProcess.java:122)
    at org.eclipse.jgit.transport.Transport.fetch(Transport.java:1201)
    at org.eclipse.jgit.api.FetchCommand.call(FetchCommand.java:128)
    ... 13 more
Caused by: java.io.IOException: There was a problem while connecting to our-git-server.local: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:603)
    at org.jenkinsci.plugins.gitclient.trilead.TrileadSessionFactory.getSession(TrileadSessionFactory.java:29)
    ... 20 more
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)
    ... 23 more
Caused by: java.io.IOException: Cannot read full block, EOF reached.
    at com.trilead.ssh2.crypto.cipher.CipherInputStream.getBlock(CipherInputStream.java:81)
    at com.trilead.ssh2.crypto.cipher.CipherInputStream.read(CipherInputStream.java:108)
    at com.trilead.ssh2.transport.TransportConnection.receiveMessage(TransportConnection.java:232)
    at com.trilead.ssh2.transport.TransportManager.receiveLoop(TransportManager.java:706)
    at com.trilead.ssh2.transport.TransportManager$1.run(TransportManager.java:502)
    at java.lang.Thread.run(Thread.java:745)
ERROR: null
Recording test results
{{ERROR: Step ‘Publish JUnit test result report’ failed: Test reports were found but none of them are new. Did tests run? }}
For example, /var/lib/jenkins/jobs/some-project/workspace/reports/SPEC-some-project-copy-ssl-file-with-all-arguments.xml is 2 hr 32 min old{{}}

This is not the case with Jenkins 2.57; we suspect the updated SSH library in Jenkins 2.58 to be the cause. We run Jenkins as well as the Git server on standard CentOS 6.9, with non-modified SSH server settings, so the expection is that this should work (or the Jenkins Git Plugin help should describe which SSH cipher/algorithm settings need to be changed).