Case # 02097703
We are suffering from this bug, and are eagerly anticipating a fix. Just wanted to post the info in case it helps anyone else, and see if there are any updates available for it yet.
After the upgrade to 9.5, our local backups began substantially longer than they had before. Critical server backups went from about 15 minutes to 90 minutes. The reason for the additional time is "a bug that under certain circumstances will cause Backup and Backup Copy jobs to recrypt cryptographic keys on every session, even if the master key hasn't been changed."
The only solutions available were to disable storage encryption completely, or reduce the number of restore points we are keeping. Neither of those are tolerable for our environment, so we are dealing with the extended backup times until it's resolved.