Have you tried restoring the phone as new, and then reinstalling the apps and data from a backup? Back before Apple eliminated the app management function from iTunes (which allowed users to sideload the apps from a local backup), I used to periodically do that just to eliminate the cruft that built up from botched downloads, poorly written apps that would build up huge caches, and storage that didn't fully release after large data transfers.
iOS has gotten better at purging garbage data (and all app restorations now need to go through the app store, so restoring from backup now takes longer and counts against my data cap), so I don't do full restorations from backups anymore. But, if you don't have any apps that are no longer available from the app store that you would like to keep, then the restore as new and reinstall from backup option could work. Generally, I prefer to work from an encrypted local backup (encryption preserves your text messages, health data, and saved passwords), otherwise restoring from an iCloud backup might leave some data out.