Almost a month is way too long no matter what the reason; bandwidth, size, etc. Things are changing over that entire time. It's hard for it to do incrementals, which it isn't if it is still doing the initial backups.
Most of these offsite backups allow you to send a "seed" on a HDD, so they can copy it in minutes to your backup.
The same thing if you need to restore. They can ship a copy back.
