Lo que puedes hacer es hacer primero un select de los ids con el RAND() obtienes toda la lista de ids ya ordenada aleatoriamente, y la guardas en la sesión, posteriormente entonces haces tu consulta SELECT normal pero solo pides una parte de tu array, de la sesion, asi no importa si cambias de pagina vas a conservar el mismo orden aleatorio.
Para obtener una parte del array usa array_slice.
Saludos
