Having actually looked in to this now with a bit more detail than "google it to check your understanding and look at the first result":
It appears you're right, and "fast" is derived from faest while steadfast is a combination of steade and... fast.
Fast friends is a perfectly cromulent phrase :)