Git related commands stop working due to an error after upgrading git/openssh to 2.4.5/6.9p1-1

After a recent git upgrade (2.4 -> 2.4.5) on the remote repo the pre-authentication step throws the following error:
git sshd[7823]: error: Hm, kex protocol error: type 30 seq 1 [preauth]

The result is that all git related commands that involve the remote repo (fetch, push...) fail when using the GUI. They fail with the above error on server, but the SourceTree GUI keeps showing the progress bar with no extra output in the "Show Full Output" window. After a while, when the server drops the connection, this is the output

FATAL ERROR: Server unexpectedly closed network connection

fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

Completed with errors, see above.

The same commands work fine through the terminal (git bash and windows cmd both work).

The git upgrade includes the following upgrades that sshd uses:

1. upgraded libssh (0.6.5-1 -> 0.7.0-2)
2. upgraded libssh2 (1.5.0-1 -> 1.6.0-1)
3. upgraded openssh (6.8p1-2 -> 6.9p1-1)

By checking the openssh mailing lists I found this explanation for the type 30 error.
> Hm, kex protocol error: type 30 seq 1 [preauth]
message type 30 is the pre-RFC4419 group exchange message. Since RFC4419 was published nearly 10 years ago support for the non-standardized message was recently removed from OpenSSH.

If I understand this correctly, it seems that a newer key exchange method has to be used when connecting through SSH by using Putty/Plink with usernames and passwords.

UPDATE:
Using SSH keys fails with the same error as well.
SSH keys start working after updating the bundled /tools/putty/plink.exe. However connecting through SSH by using Putty/Plink with usernames and passwords still fails with the same error.