I'll suggest an architectural change... your script does a lot of directory readings, reading of files, randomizing and sorting, and it's doing all of these things on every page hit. How often do you really need to change the image gallery? If you can live with more infrequent updates, have a cron job which does this work and stores the results in a file. Then your SSI just opens this file, reads the image data and generates the HTML.
Even if you have the cron job run once a minute, you are only doing this work once a minute instead of once for every page hit.