I was having the same issue and was only able to resolve it by doing a backup, erasing all content and settings, then restoring from the backup I made. I have a 64gb iphone 12 and I was constantly running out of space regardless of what I was deleting. After I did this my space used dropped to around 40gb, so it freed up almost 24 gb of nonsense.
iOS 16 instructions
BACKUP FIRST
Settings > click your name at the top > iCloud > iCloud Backup > Backup Now
RESET
Settings > General > Transfer or Reset Phone > Erase All Content and Settings > Continue
RESTORE
Follow the instruction from the blank screen to sign into a wifi and your apple account first, then restore it from the backup you just made. It will take some time to download a lot of the apps again so plug it in and let it do its thing for a while. You'll have to set up FaceID and sign into a lot of apps again, but the space that was created from the process seems worth it to me.
Hope that helps!