Can you check if the settings “send as sms” in the message settings of the new iPhone 13 was on?

Also, did you change your plan recently with the new iPhone?

I visited a local Koodo kiosk and they were able to help me. I had not activated the new SIM card that came with my phone. Alternatively I could have just transferred the old SIM card into the new phone. I did not see anything in the literature with my new phone that this was required. Lesson learned!