图像缓存大小会增加加载时间

I host a website that as a part of it's service the website creates cool little PNG avatars for users based on their skin in a game.

I am caching all images in a cache directory for 4 hours to prevent hitting the game's servers and to decrease loading time for the images, but after a year or two of doing this I noticed that load times of avatars increase as there are more cached images in the directory, which looks strange to me because I do not make my script iterate through the entire directorty until it finds the cached image it was looking for.

And here are some benchmarks in cURL:
First test; 400 cached images:

-------
    time_namelookup:  0.000
       time_connect:  0.093
    time_appconnect:  0.000
   time_pretransfer:  0.093
      time_redirect:  0.000
 time_starttransfer:  0.452
                    ----------
         time_total:  0.452

Second test; after deleting all of the cache:

   time_namelookup:  0.000
      time_connect:  0.093
   time_appconnect:  0.000
  time_pretransfer:  0.093
     time_redirect:  0.000
time_starttransfer:  0.249
                   ----------
        time_total:  0.249

So, is there any specific reason why the loading time is decreased with less cache in the directory? And is there a way to optimize that?
Edit The way the requests are made is that whenever somebody requests an avatar the script checks if there is a cached image with his username.
It does that with PHP's file_exists()