Yeah, what others have said try deleting browser data, iMessage attachments, MMS attachments if any. Nuclear option is backup and restore.
I have 14.1 gb of photos + videos but not a single one takes up space on my phone. Photos doesn't even appear on the list of apps using storage in the iPhone storage settings menu. I have optimize photos setting enabled and use iCloud for everything (I pay for the 50gb storage option). It automatically uploads everything and has worked perfectly for me so far. You may want to consider doing the same?