I can confirm you can get them from Gold and Titanium Crates at a 1/30 and 1/15 chance for each respectivelyIf I recall correctly, not every world will have a sword shrine, but every shrine will have a sword.
I'm not sure on this much though. Can you send a screenshot so I can see how much is mined?
You may need to make a new world exclusively for this.
Edit: I think you can also get them from the Gold and Titanium crates.