What you're describing normally happens if you have low storage. How much space do you have free?
5.5gb
Safari does clear caches/temp files automatically so it's not unusual to see 'cleaning' on the icon. However this normally occurs more frequently when you are low on disk space.
With regards to losing history, I'm a little stumped there.
It's really annoying
Maybe restore?
Well, a complete restore is always a good nuclear option to try and iron out any software issues. If you have the patience for it, I'd definitely go ahead with that.
I have to choice..
Via iCloud or iTunes?
Captain's discretion; either or.
I normally just do Settings> General> Reset> Erase all content and settings.