I reformatted about a month ago and from hitting the big button to the desktop appearing takes 40 seconds. So no, it should'nt take that long.
In msconfig have you a lot of startup programs ticked. (Mine = 9)
In your programs menu under "Startup", have you any entries. (Mine = 0)