Hello there, we faced the exact same error.
In our case, it was Veeam trying outdated encryption methods, therefor not able to install required components.
It only tries to install that when ADDING THE MANAGED LINUX SERVER, not when rescanning.
You can check that - /var/log/messages or /var/log/syslog or wherever your disto logs to: There will be ssh connection errors - very obscure, because a lot of other connections actually work! It's only 1 or 2 tries that fail (Veeam seems to use different SSH-settings for different tasks!). The error only pops up when you try to add the server as a new managed linux server, not when rescanning it etc.
If that's the case, you'll have to edit the sshd config, reload ssh, delete the managed linux server and readd it.
Here's the part of our sshd config:
# Specifies the available KEX (Key Exchange) algorithms. //recommended von Mozilla
#KexAlgorithms curve25519-sha256@libssh.org,ecdh-sha2-nistp521,ecdh-sha2-nistp384,ecdh-sha2-nistp256,diffie-hellman-group-exchange-sha256
KexAlgorithms curve25519-sha256@libssh.org,ecdh-sha2-nistp521,ecdh-sha2-nistp384,ecdh-sha2-nistp256,diffie-hellman-group-exchange-sha256,diffie-hellman-group1-sha1
#MACs hmac-sha2-512-etm@openssh.com,hmac-sha2-256-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-512,hmac-sha2-256,umac-128@openssh.com
MACs hmac-sha2-512-etm@openssh.com,hmac-sha2-256-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-512,hmac-sha2-256,umac-128@openssh.com,hmac-sha1
These are mentioned here:
https://helpcenter.veeam.com/docs/backu ... ml?ver=100
and here:
https://www.veeam.com/kb2061
Isn't SHA1 outdated by now? Why is 1 or 2 specific connections failing when adding a managed linux server, while all other ssh sessions seem to work fine (evidenced by the ssh logs, as well as /tmp/veeam* folders being created)