That is strange, maps should normally load in < 1 second. They can appear slower if other scripts are executing from the theme or other plugins.
You can check if it’s something else by deactivating ALL of your other plugins and switching to the 2012 theme for a few minutes. If you get the site in that state, and it still seems slow, send me an email with the contact form and I’ll trace it for you.
You can also try the MapPress setting to load the maps last (in the bottom ‘misc’ section). That should prevent the map loading from delaying other scripts on the page.