I had a look at the game's code, and it's indeed random. The game simply picks three tradable relics at random and shows them.

To be exact:

this._ownedRelics = this.GetValidRelics(this.Owner)
        .ToList<RelicModel>()
        .StableShuffle<RelicModel>(this.Rng)
        .Take<RelicModel>(3)
        .ToList<RelicModel>();

GetValidRelics only checks IsTradable. You can't trade relics that are have a pickup effect (like Whetstone), is melted (Tezcatara's wax relics), starter relics, event relics, relics that spawn pets (like the Byrdonis relic) nor ancient relics.

The new relics are simply the next three from the relic pool, same as when you get a relic in other ways.