I don’t think it was ever common for people to literally use the phrase “steadfast friends”. The word “fast” by itself meant (and still means sometimes) something like steady or firmly stuck. So “fast friends” per se was always a perfectly fine phrase. It hasn’t been shortened from some other form.

People trying to explain the origin of the phrase “fast friends” point to the word “steadfast” as an example of where this sense of fast persists. You might also notice the same meaning in our words fasten, colorfast, etc.