Alright, so I could fix it. Very easily. I think you were right about the “changed host key”.
Solution: Open Duplicati, edit the configurations of your backup, then go to Destination and hit Test connection, you will get a modal that offers to change the host key, hit OK and save the settings. Manually trigger a backup job and everything should work again.
Thanks for your help!