Here's a nice article on ship naming. Minister of National Defence has the final say.
Not a huge River class name fan but some of those names are emblematic of the RCN.
You could the the Provincial class, which would be interesting.
Quebec, Yukon (though named for the River IIRC), Ontario have been used previously. Newfoundland was an HMS not HMCS.
Tribal Class we could get close to the full 15 ship names
- Iroquois
- Athabaskan
- Huron
- Haida
- Micmac
- Nootka
- Cayuga
- Algonquin
- Ojibwa
- Okanagan
- Onondaga
- Assiniboine (take the river name and make it a tribal name).
That brings you to 12 with previous battle honours. Add in Cree (largest nation in Canada), Inuit, Metis, maybe remove some that are language groups and/or don't match modern tribal naming conventions.
Edit:
Went out and found a list of the first nations in Canada. There are some modified spellings from the original ship names, Mi'kmaq is a good example, and an example of a changed name is Iroqouis =>Haudenosaunee. I think you could make the exception that if you are changing out ships crests for first nations artist ones, you can change the spelling/name and the legacy lives on.