Search for new pics takes forever.

[Hercules24]

As my gallery grows each week it takes the server more and more time to look for new pictures when using the batch add files button.
After a while the server timed out with a 500 (internal server) error, but by manually re entering the searchnew.php url the opload directory screen came back.
Currently it takes 3 times of reloading the searchnew.php to finally get the screen to browse the directories for new pics.
The adding of pics itself goes fine, it's just taking more and more time for CPG to get to the directory screen.
Changing maintenance settings and setting upload boxes to 1 didn't change anything.
Currently I have 27,500 pics online and I'm not planning on retiring yet
Any ideas how to speed up this process or allow the server more time before going into 500 mode?
Gallery can be found here: http://www.kuikens.com/pictures