Short-circuiting or not, the result is the same, that's why short-circuiting exists, because testing the rest would make no difference to the result of the expression. (Both
or are short-circuited)
But yes, that's totally unreadable and I wouldn't write it that way. Anything with multiple NOT's in it is just.. Nope.
So I'd write:
while not (choice == 'y' or choice == 'n'):
or better yet
while choice not in 'yn':
if choice == 'y' or choice == 'n':
And if a condition gets really long and difficult to read, split it up into multiple expressions, assigning results to variable names that explain what's tested, and then combine those variables with and/or/not
If something looks really complicated and unreadable, then typically there's a better way to formulate it.
A comment stating the intention in natural language can help somewhat as well.