block-random-enhanced and first-time load performance

I'm using the block-random-enhanced plugin with Gallery 1.5.5. When I load my page, it takes 3-5 seconds and the random block appears fine. After this, when I hit F5 to refresh the page, reloads take 1-2 seconds. I'm wondering what's causing it to be so slow on the first load and what I can do to speed it up. I'm using a php include() to put the block into my index.php.