This shouldn't be a common thing. Possibly every 5-10 songs, but not after each one. I would simply try uninstalling and reinstalling Spotify, seeing as all your music is tied to your account, not the application. Otherwise, see if you can erase the cookies by going through "All Programs" on Windows, and "Applications" on Mac.
I hope this helps! If it did, remember to mark this as a solution! 🙂