A linear scan is the best that I know how to do, if the sets are represented as sorted linked lists. The running time is $O(|A| + |B|)$.
Note that you don't need to compare every element of $A$ against every element of $B$, pairwise. That would lead to a runtime of $O(|A| \times |B|)$, which is much worse. Instead, to compute the symmetric difference of these two sets, you can use a technique similar to the "merge" operation in mergesort, suitably modified to omit values that are common to both sets.
In more detail, you can build a recursive algorithm like the following to compute $A \setminus B$, assuming $A$ and $B$ are represented as linked lists with their values in sorted order:
return A # return the leftover list
return B # return the leftover list
if A < B:
return [A] + difference(A[1:], B)
elsif A = B:
return difference(A[1:], B[1:]) # omit the common element
return [B] + difference(A, B[1:])
I've represented this in pseudo-Python. If you don't read Python,
A is the head of the linked list
A[1:] is the rest of the list, and
+ represents concatenation of lists. For efficiency reasons, if you're working in Python, you probably wouldn't want to implement it exactly as above -- for instance, it might be better to use generators, to avoid building up many temporary lists -- but I wanted to show you the ideas in the simplest possible form. The purpose of this pseudo-code is just to illustrate the algorithm, not propose a concrete implementation.
I don't think it's possible to do any better, if your sets are represented as sorted lists and you want the output to be provided as a sorted list. You fundamentally have to look at every element of $A$ and $B$. Informal sketch of justification: If there is any element that you haven't looked at, you can't output it, so the only case where you can omit looking at an element is if you know it is present in both $A$ and $B$, but how could you know that it is present if you haven't looked at its value?