xdelta isn't a complete solution, but it may help with deduplication. Note
that you may need to change the parameters to increase the deduplication
ratio.
GPG has built-in compression, but if you want more compression you may want
to use an external too; if you do, don't forget to disable the built-in
compression because it would just make things slower and likely increase the
size slightly.
Also, you can encrypt your private key with a symmetric key algorithm and
store the encrypted private key along with the backup so that you can recover
the backup by knowing the key used for the symmetric encryption.