I'm using a G4 iBook, and yea the startup tends to be slightly slower compared to usual PC Windows startup. Estimated of approximately 6-8 minutes on average.

35 minutes? That's a bit too much. Try either Onyx (as stated by oh-so-many si-fus above this post) or some other maintenance alternatvies. There are plenty of freewares out there that does the job, different in utilities but all targeting the same objective.

Seriously though, I don't htink it's necessary for you to reformat the iBook. Waste of time only.