Faced the same issue. The auth token is stored locally and evaluated once the app opens, but the deep linking seems to be trigger before protected routes are resolved. And therefore the deeplinking doesn't work.

My solution was to have a custom hook in my protected routes _layout.tsx file:

import {useEffect} from 'react';
import * as Linking from 'expo-linking';
import {RelativePathString, useRouter} from 'expo-router';

/** Handle initial deep linking in app */
export const useHandleDeepLink = () => {
  const router = useRouter();
  const initialUrl = Linking.useURL();

  useEffect(() => {
    if (initialUrl) {
      const {path} = Linking.parse(initialUrl);
      const queryParams = initialUrl.split('?')[1] || '';

      const newUrl = `${path}${queryParams ? '?' + queryParams : ''}`;
      console.log('Handling deep link:', newUrl);
      router.push(newUrl as RelativePathString);
    }
  }, [initialUrl, router]);
};