There's definitely a problem somewhere, Zenphoto is clearly not supposed to run that slowly...
What does the /cache folder look like? Are there folders of images in there? What are the permissions on the sub-folders of /cache (if there are any)? What about the images?
My guess is that it's having trouble detecting whether the images have been cached or not, but I'm not sure why.
Second thing, the images you're trying to display are rather large (looks like about 6 Megapixels). If you resize them down to 800x600 or 1024x768 or around there, they will process and load much much faster. We recommend this for any shared host where processing is slow, and the same would be true of any web-based gallery software.
Still, they should not be re-processing each time the page is loaded, that's definitely a problem. We'll help you figure it out.