The phrase גב המזבח actually dates back to Tanach (Yechezkel 43:13). Perhaps the phrase גבי המזבח is Mishnaic Hebrew, while גב המזבח is Biblical, and over time the latter morphed into the former.
Notice that the phrase גב המזבח isn’t just uncommon in Mishnayos; Eduyos 6:1 is its only appearance. Based on the above, this can be justified by noting that Eduyos dates back to Bo Bayom (Berachos 28a), which was in Rabban Gamliel’s time, two generations before Rebbi Yehudah HaNasi; if I’m correct that גב eventually morphed into גבי, the fact that Eduyos is older than the rest of Shas could have preserved the old spelling, before it changed.
The same could apply for its transition from מזבח to המזבח. The phrase גב מזבח never appears anywhere before the close of Shas: the earliest I see its usage is Rashi to the cited passuk in Yechezkel; both later usages I see are people quoting this Rashi.
On the other hand, גבי מזבח appears just twice in Mishnayos (Sukkah 5:5 and Temurah 6:4), once in Yerushalmi, and seven times in Bavli, while גבי המזבח appears 27 times in Yerushalmi and 24 times in Bavli. This would seem to indicate that this change took much longer to happen than the previous one.
(Note that these numbers aren’t totally accurate since Braisos are included in Bavli and Yerushalmi, but the general thrust of the point should remain the same. If someone wants to do their own search and divide it up further by generation, feel free.)