Maybe remove the rule that any loss requires the start of a new streak, but give a time limit to the the challenge -- say, 1 week since your first win. Since the penalty for losing is a 24 hour ban from the frontier, losing limits the amount of time you have to complete the challenge but doesn't kick you out entirely. I think that would be both challenging and achievable, although it would put more pressure on brains for taking challenges in a timely manner.
Another option is to give each streak a number of "lives" -- something like 2-3. Each loss on your current streak removes a life, but your streak isn't discontinued until you lose all of them. This is less time-sensitive and as such might be a more realistic framework to use.