From my understanding the best way to do this is find the leaf (if it exists) and find your way up the tree. In that case the complexity will be O(N) to generated.
There are two steps here, and it's not clear which you think might take $O(N)$ time.
The first step is finding the leaf; yes, if you take the approach of examining each element individually, this will obviously take $O(N)$ time if there are $O(N)$ elements. On the other hand, this isn't necessarily the only possible algorithm. If we have our $N$ elements, then we can build a data structure (say, a hash table) to look up the elements quickly, if faster lookup is deemed necessary.
The second step is generating the authentication path; yes, generating the entire Merkle tree (and computing the root) will take $O(N)$ time, and there's no way to get around that. On the other hand, once we have constructed the tree, we can often save the values of intermediate nodes. In the most straight-forward approach, we can just save all the intermediate nodes; this requires $O(N)$ memory; on the other hand, constructing the authentication path just involves copying the appropriate node values, and that can be done in $O(\log N)$ time.
