I don’t believe it’s possible to have random posts on every load along with pagination. If that was the case, the posts would randomize when you went to the second/third etc.. pages, and you’d see posts you’ve already gone through.
Instead, WPSP caches the random order in a session so you can paginate through the posts without any duplication.