When you say that the album is being regenerated from scratch, do you mean that all of the slide images are actually regenerated? Look at the time stamps on the output files. Some things have to be regenerated, even if you are adding only a single image - the index.html page on which that image appears, the JSON files (if the skin you're using requires them), sometimes the slide pages (if the skin you're using requires them, and if they have things like a thumbstrip), and so on. But the big time-takers - processing images and videos - should not happen every time.

And of course, do not choose Make All, which tells jAlbum to do exactly that, make everything from scratch, including all the image files. Just click Make Album.