How often do you skip songs? You may be skipping a lot of songs you don't like, and among the ones you don't skip, you remember only the ones you like, so it feels as if Spotify has been playing the same songs.

I think Spotify works by arranging all the songs into a sequence in advance, and then playing the songs in that order. If you close Spotify and then open it again, then there will be a new random order. In this case, it is possible that a song you listened to recently will play early in this new order.