Ignore cache in preprocess function
If it's a limited set of pictures that you have then I would just write a custom formatter that displays for example an image tag with a data attribute that has your list of image paths (maybe with the first image already set as non-JS fallback maybe). then you just need small bit of JS that picks one of those randomly and sets it as the actual src attribute. Your page is fully cacheable then and while it might still be a noticeable delay until the image shows up, that can even happen with static image links on slower connections. 

And it will certainly be much faster than an ajax request.

The placeholder approach might also work and Drupal supports that kind of out of the box with dynamic page cache, doesn't need a reverse proxy or so for that. but you would have to disable the internal page cache then on that page. See http://www.qed42.com/blog/lazy-builders-drupal8 for an example on that. 

The way that works with Dynamic Page cache is that the whole page with the placeholders is cached, and then calls the defined lazy builders which returns the actual content for the current request. You would want to use a similar approach as with JS, prepare all image urls for example already as arguments and then just pick one from that array and render it.