$\gcd(a,b)$ is the least positive linear combination of $a$ and $b$ Let $l$ be the smallest positive linear combination of $a,b\in \mathbb{Z}^+$ i.e.,$$l := \min\{ax+by >0 : x,y\in\mathbb{Z}\}.$$
Now, according to @Brahadeesh's answer here, Proof for $\gcd$ being the smallest linear combination of $a,b \in \mathbb {Z}$., we can show that $l\mid a$ and $l\mid b$ (simultaneously).
But, consider $k>l$ such that $k\in \{ax+by >0 : x,y\in\mathbb{Z}\}$. Then, is it possible to show that $k\not\mid a $ and $k\not\mid b$ (simultaneously)? This indirectly gives us that there are no common divisors of $a$ and $b$ that are greater than $l$ which then proves that $l = \gcd(a,b)$.
The direct proof of the fact that $l=\gcd(a,b)$ would be to show that $c\mid a $ and $c\mid b \; \Rightarrow \; c\mid l$, which is quite trivial from the definition of $l$. However, I don't want to make use of this fact and instead want to show that 

Claim: If $k>l$ such that $k\in \{ax+by >0 : x,y\in\mathbb{Z}\}$ then $k\not\mid a $ and $k\not\mid b$ (simultaneously).

Thanks in advance.

I’m not sure that there’s much difference between what you want and the “direct” proof. I would argue as follows. Suppose for contradiction that $k\vert a$ and $k\vert b$. Then $k\vert l$, and by an identical argument $l\vert k$. Therefore $k=l \not> l,$ a contradiction.
