i'm using AVRdude programmer using a home made cable on Linux and i definitely need to erase before i program.
i'd imagine this will be the same for all setups.
as for verifying, i don't think i have ever had my setup fail when there was no problem with something else (like i've forgotton to power the AVR or something) but i usually leave it on just to check everything is ok.
so it typically takes between 30 and 60 seconds for me to flash an AVR with erase, program and verify steps.
how long is it taking you?
you are using a serial port programmer on a windows platform if i remember rightly?
i followed this http://www.instructables.com/id/E5H5UDWB5UEUKIKV8V/?ALLSTEPS
first time round and it has instructions for windows as well.
maybe it's worth you trying that way if your getting times much over a minute.