Changing the wp_link_pages() function is an option, but randomizing either the page numbers or page links may be detrimental to the user’s experience as he’s expecting a normal page link structure while noticing random page numbers, e.g. in the post’s URL.
However, there exists a content_pagination filter that lets you alter the post’s $pages array. Simply shuffling this array would suffice, however, this does neither guarantee a static page order nor does it exclude the possibility of page repetition, as the shuffle is executed on each page load.
You could solve both these problems by using array_multisort() in combination with mt_srand(), as explained in this answer, and seed the random number generator with e.g. the post’s ID—but then, every user is served the same (pseudo-random) page order, and one could argue what’s the use of shuffling the pages at all.
You could mix in the user ID (if any) in the seed, e.g. by multiplying the post ID with the user ID, to increase the chances of giving each registered user their “own” static page order that varies across posts. In the end, it really depends on what you want, and how far you are willing to go with it.
Code example (seeded with post ID):
function shuffle_pages( array $pages, WP_Post $post ): array {
mt_srand( $post->ID );
$order = array_map( function ( $val ) { return mt_rand(); }, range( 1, count( $pages ) ) );
array_multisort( $order, $pages );
return $pages;
}
add_filter( 'content_pagination', 'shuffle_pages', 10, 2 );