I have little experience with device triggers, because I avoid them for several reasons. I use state and numerical state triggers instead. They are way more flexible and predictable, because they are not device dependent. So I would rewrite it to use state triggers on the entities (from: home and to: home) first. Also for the zone triggers.
Also check in the history graph of Home Assistant if the device trackers actually change soon enough. I seem tot remember fritzbox is particularly slow in marking devices offline. Maybe a ping sensor is more reliable, provided you set the phone not to switch mac address all the time when on the home wifi.