I highly recommend Tarsnap [1] for your off-site backups. It has a tool that does pre-encryption with user-controlled keys, deduplication, and a reasonable price; for your use case, about $1500 a month, though more in the first month for bandwidth. I've used them for years.
1: https://www.tarsnap.com/