Is that really a surprise?

Hmm...

I use AnySoftKeyboard instead of the default android keyboard or the Samsung keyboard just to preemptively avoid these kind of “issues” creeping up in the future.

Should I still be worried?

Is there a way to sandbox or scope the software keyboards to never see the network (wired ethernet, Wi-Fi, LTE, 5G or otherwise) on stock Android 13 ?

Other than:

Settings > Connections > Data Usage >

Allowed networks for apps > {app} > Wi-Fi only (and not use Wi-Fi) or Mobile data only (and not use Mobile data)

and

Mobile data usage > {app} > Allow background data usage > Disabled

Moreover, there is no "Network Permissions" setting option from what I can see even within Permission manager > Additional permissions.

Can you point to where it says that in the report? It actually says:

an IME will commonly reach out over the network to a cloud-based service for suggestions if suitable suggestions are not available in the input method’s local database.

So it doesn't send "every key typed".