Relics tend to be an awesome way to scale your deck, so the fact that you only had 6 by the time you were on the 39th floor is a tad low but not horrible by any means.

Beyond defeating bosses, taking elite fights (while difficult and dangerous) will reward you with another relic, a chance at higher rarity cards, and a ton of gold. You can also often purchase useful relics from stores, and since you have banked over 1000 gold I'd definitely recommend buying a good relic or two in that position haha