This issue may be relevant for other Duplicati users:
Duplicati is configured to backup via SSH on a Debian webserver. After this webserver was updated, the backup failed with the error message "Algorithm negotiation fail".
SFTP via FileZilla is still possible, using the same credentials.