An option which seems to match most if not all of your requirements is borgbackup. As for the private key, borgbackup has several modes, the default being one w

An option which seems to match most if not all of your requirements is borgbackup. As for the private key, borgbackup has several modes, the default being one where the private key is stored on the server but encrypted with a passphrase; if you don't like it, you could use the mode where the private key encrypted with the passphrase is kept locally and then backup that (very small) key file separately.