Bueno, acá te dejo un código que encontré en Google:
<?php
$total = "11"; // Numero total de imagenes
$extension = ".jpg";// Definimos la extension, puede ser .jpg, gif, bmp, etc.
$carpeta = "imagenes/aleatorias";//Carpeta con las imagenes
// De aqui para abajo no es necesario modificar nada
$start = "1";
$random = mt_rand($start, $total);
$image_name = $random . $extension;
echo "<a href='$carpeta/$image_name'><img src='$carpeta/$image_name' border='0'></a>";
?>
Como ves, todo ya está explicado con comentarios en casi todas las líneas.
Lo único que yo he agregado es que cuando se muestre la imagen se le pueda hacer clic para verla más grande (su tamaño original).
pd: no he probado el código ni lo he revisado detalladamente, pero supongo que todo está bien.