A comment from Robert gave me the key-word I needed to be able to do some research myself, so I'll post what I have learned and how it should be done in the first place. I am not sure what the best way to transition from my situation to the goal is in general, but I think this varies depending on outside constraints. For me it is best to re-encrypt all the data with the newly presented approach since there are no external constraints.
What to do in the first place?
Instead of just encrypting all the data with a single key, a new key should be generated for each file. These keys should be wrapped using a master-key and stored alongside the file. The master-key is your client secret and used purely for wrapping and unwrapping keys.
Why should it be done this way?
Key-wrapping algorithms have a number of properties including confidentiality, authenticity and, in particular, the property that an attacker can only see when two plaintexts match. Using the property that cryptographic keys have high entropy, this gives us a larger bound on the number of keys that can be wrapped.
- Better invocation limit or better collision probability
NIST specifies a limit of
2^32 invocations of AES-GCM per key when not using deterministic
96-bit nonces to keep the probability of a collision below
2^-32. Since I used randomly created 96-bit nonces, this limit also applies to the number of invocations I should limit myself to.
When using the key-wrapping approach from above by wrapping the
256-bit keys, the limit of invocations is increased drastically. The number of invocation for wrapping
256-bit-keys, that can be done with one key while keeping the same collision probability of
2^112 (source: maths). In the same fashion, the number of invocations for wrapping 256-bit-keys can be reduced to
2^96 while reducing the probability of a collision to
- Changing the key is easier
Aside from the increased number of invocations it is now possible to update the master-key by only re-wrapping the file keys. This may still be a tedious task, but it is still far better and cheaper than to re-encrypt potentially gigabytes of data per file.