I very recently started using borgbackup. I’m extremely impressed with how much it compressed the data before sending, and how well it detects changes and only sends the difference. I have not yet attempted a proper restore from backup, though.

I have much less data I’m currently securing (~50gb) and much more uplink bandwidth (~115mbps) so my situation isn’t nearly as dire. But it was able to compress that down to less than 25gb before sending, and after the initial upload, the next week’s backup only required about 100mb of data transfer.

If you can find a way to seed your data from a faster location, reduce the amount you need to back up, and/or break it up into multiple smaller transfers, this might be an effective solution for you.

Borgbase’s highest plan has an upper limit of 8TB, which you would be brushing right up against, but Hetzner storage boxes go up to 20TB and officially support Borg.

Outside of that, if you don’t expect the data to change often, you might be looking for some sort of cheap S3 storage from AWS or other similar large datacenter company. But you’ll still need to find a way to actually get them the data safely, and I’m not sure if they support differential uploads like Borg does.