I agree. I‘ve played mix frost/fire and it was no problem to play hell with cheap melody runeword on a +2 bow base .
But frost is way more fun than fire. I would try frost/strafe next time too. Frost as primary skill and strafe just for immunes.
Remember you can switch weapons and use for example melody for frost and switch to wws for strafe.
The frostmaiden dont need faith or ice to kill fast enough.