A modification of Dror's comment.

This probabilistic algorithm worked for me.

The main idea is to pick some $z$, compute $m=n - z^2$, factor $m$ with trial division and express it as a sum of two squares if possible. The probability of finding prime $m=4a+1$ or $2p$ is high enough for practical purposes.

The algorithm:

1. z:=0
2. z:=z+1
3. m:=n-z^2
4. if can't trial factor m goto 2
5. if m=x^2+y^2 (the factorization is known) then x^2+y^2+z^2=n. Done
6. goto 2


Here is a pari/gp program and example:

    pl=10^8;
    default(primelimit,pl);
    {
    twosquares(n)=
    local(K,i,v,p,c1,c2);
    K=bnfinit(x^2+1);
    v=bnfisintnorm(K,n);
    for(i=1,#v,p=v[i];c1=polcoeff(p,0);c2=polcoeff(p,1);if(denominator(c1)==1&&denominator(c2)==1,return([c1,c2])) );
    return([]);
    }
    
    {
    threesquares(n)=
    local(m,z,i,x1,y1,j,fa,g);
    for(z=1,n,
    m=n-z^2;
    print1(z," ",);
    fa=factor(m,pl);
    g=1;
    for(i=1,#fa~,if(!isprime(fa[i,1])||(fa[i,2]%2==1&&fa[i,1]%4==3),g=0;break; ));
    if(!g,next);
    print("\nfound ",z," "," m=",m,factor(m));
    j=twosquares(m);
    print("j=",j);
    x1=abs(j[1]);
    y1=abs(j[2]);
    return([x1,y1,z]);
    );
    }
    /*
    ? n=nextprime(10^100)*nextprime(2^1000+1000);
    ? t=threesquares(n)
    ? ##
      ***   last result computed in 1min, 2,030 ms.
    ? t[1]^2+t[2]^2+t[3]^2-n
    %25 = 0
    ? round(log(n))
    %26 = 923
    */