It takes me around 15-20 minutes to change strings if I'm in a hurry, though I'd usually leave a bit longer to give the guitar a chance to settle. I often take them all off so I can wipe the fretboard and dust the headstock, and it seems to be quicker that way too. Never had huge problems with tuning stability once I've done it.

A peg winder is invaluable, and I have one in each instrument case. Only problem is that the notch for pulling out bridge pins seems to get worn out on the cheap plastic ones- I have a separate tool for that. And since discovering that the bridge pins on my bouzouki are made of putty I always have spares on hand.