If you receive the error "Permission denied (password)," check that the credentials used to connect to the server are valid.
If you receive the error "Unable to establish connection to host," ensure there are no firewalls blocking port 22 between the Veeam backup server and the Linux server. As an isolation step, try using PuTTY to make an SSH connection to the Linux server from the Veeam backup server using the same credentials that are specified in the Veeam backup console. This will help to ensure that it is possible to connect to the server outside of the Veeam software.
If Veeam Backup & Replication displays an error regarding negotiation, review KB2061 for a list of compatible Ciphers, Key Exchange Algorithms, and MAC Algorithms.
If issues remain, please contact Veeam Support.