That's not how pagination works. You need to define a dataset, which can consist of randomly sorted database entries, and the pagination makes it possible to only see part of it. If, however, every call is random (which I think you are doing, because you write SQL+PHP), then you cannot go to the previous page to see the items you previously saw. It'll always be random, and you can just leave out pagination and add a refresh-button instead.

You can test the behavior by going to page 2, then 3, then 2. You should always see different content, even though pagination should show you the same on page 2 as you already had the first time you opened page 2.

If you don't want to rely on JS to download an entire dataset, you'd have to cache the dataset on the server, which might explode depending on the store visitors. That's why, instead of using rand(), I suggest coming up with a different, deterministic algorithm, which shows new content every now and then but can be calculated and keeps pagination functional.

Maybe use a cookie to store a seed which you use to randomize the search, and give the seed a timeout, which you refresh on every page visit, on which the timeout is still active. This way, the user will see the same stuff when they surf around, but if they come back after some hours (timeout), they will be greeted by new and exciting things...