We don't know when Bashir entered the usual SF Academy (only that he did) or when he graduated (only that he did), so the extra four years or whatever could be slotted in various places. We have no clear-cut reason to think that Bashir would have graduated at a rank higher than the usual Ensign, so slotting the extra years after graduation and before DS9 probably works best.
But we also know Bashir was still at the Academy as late as 2367, according to "Explorers" ("four years ago" from that 3rd season viewpoint). Or at least that he was at a New Year party that preceded his graduating. Perhaps he completed Starfleet Academy by 2363 and then did medicine at Starfleet Medical Academy, Federation Medical Academy or some other Academy for the next four years?