For config files, I use tarsnap. Each server has its own private key, and a /etc/tarsnap.list file which list the files/directories to backup on it. Then a cronjob runs every week to run tarsnap on them. It’s very simple to backup and restore, as your backups are simply tar archives. The only caveat is that you cannot “browse” them without restoring them somewhere, but for config files it’s pretty quick and cheap.

For actual data, I use a combination of rclone and dedup (because I was involved in the project at some point, but it’s similar to Borg). I sync it to backblaze because that’s the cheapest storage I could find. I use dedup to encrypt the backup before sending it to backblaze though. Restoration is very similar to tarsnap:

dup-unpack -k keyfile snapshot-yyyymmdd | tar -C / -x [files..] .

Most importantly, I keep a note on how to backup/restore: Backup 101

No static IP required ! I use it on my phone over LTE and it works great. Same goes for the NAT, I use it at work to where my laptop sits behind a NAT and I don’t have any issue.