The primary problem to tackle in restic is when to do this, and how to do it concurrent with other processes (because it will take a very long time). A great time to do this would be when prune is rewriting packs to remove unreferenced objects – it can simply write out the new packs using a new master key. This would be effectively free.
A secondary problem is that re-encrypting everything necessarily means retrieving everything from storage. This can be an issue for repositories stored in cloud storage systems that charge egress fees. If a repository is stored in S3, it might be substantially cheaper to run this process on an EC2 instance since the data would never leave AWS, but other object storage systems like B2 don’t lease on-premise compute power so the egress fees would be unavoidable.
In cases where the repository is kept locally and synced to object storage, cloud storage egress fees aren’t an issue, but the entire repository has to be re-uploaded. For larger repositories, this could easily take months. Depending on the implementation, you may also need enough storage capacity to store two copies of the repository (or at least two copies of every pack that needs to be rewritten) but probably only if a shared lock is used. (An exclusive lock means no concurrent access, and the rewrite process could delete old packs immediately after they are re-encrypted with the new key.)
IMO we should immediately update the documentation, then figure out what the implementation would look like.