There’s a shortcode for that!
[random max=* id=* template=*]
Because it’s a gallery, it will only show thumbnails. It will also split up into pages based on the setting in Gallery->Options on the “Gallery” tab “Number of images per page”.
As to its usage:
max is required, and will be the number of random images you want to display.
id is optional. If you don’t include it, it will pull random images from all of your galleries. If you include it, it will only take images from that gallery. You can only specify one gallery.
template allow you to use some of the other gallery templates like caption.
Example with 6 images from from the gallery with id 3:
[random max=6 id=3]
Example with 4 random images from all galleries with captions from the caption template:
[random max=4 template=caption]
Have fun and let me know if that works out for you.