I have problems with MIUI 13 and Wireless Android Auto (via AA Wireless USB Adapter) on the Mix 4 too. Under 12.5 everything still ran without problems. I also know 4 people from another forum who have the same problem with the Mi 11 / Ultra.
We have a wireless connection (the AA Wireless Box is recognized and connects) but the connection disconnects constantly. The cause is cell changes. MIUI disconnects the WLAN with every LTE/GSM cell change and this interrupts the connection to Wireless Android Auto. The problem has existed since the first MIUI 13 version and is still present in the current weekly/stable.
I can confirm this bug on my stock Mi10 with miui13 and so isn't a Xiaomi EU problem but a MIUI base problem. I think isn't exactly the cell Change but when miss temporary connection on a "no network area" then when connection come back android Auto immediately stuck (we talk on wireless connection only) I test this on my car using Carsifi dongle and on my friend car with native android auto wireless and get same problems so can confirm isn't a dongle problem, then I get my brother Realme phone and try on my car and have no problems using my procedure to reproduce the bug.
Now how to reproduce the bug:
1 connect wirelessly to andorid auto
2 use any app (I'm using maps and move around the map using finger)
3 disable network connection toggle from phone status bar (will Keep work without an internet connection)
4 enable again network connection toggle and android auto wireless will immediately stuck.
Using this step I can confirm other phone have no problems. I sent a feedback to xioami and hope other of you can send feedback too. Please let's me say if you find a fix