if the medium changes, the speed changes and thus the wavelength of the same sound also changes?
Yes, this is the case. Although, there's a small error in your way of thinking. The frequency $f$ and the wavelength $\lambda$ are not proportional but inversely proportional to each other. The constant of proportionality being the speed of sound $c$ (I will use $c$ as it seems to be used more often but it is the same quantity).
To showcase this all you have to do is just solve for one of the two. For example
$$ c = \lambda f \implies f = \frac{c}{\lambda} \implies f = c \frac{1}{\lambda} \tag{1} \label{1}$$
The same, of course, holds for the wavelength with
$$\lambda = c \frac{1}{f} \tag{2} \label{2}$$
To provide some intuition, let's see use the "more traditional" formula for speed. This is
$$ c = \lambda f \overset{f = \frac{1}{T}}{\implies} c = \frac{\lambda}{T} \tag{3} \label{3}$$
where $T$ is the period and as can be seen it is equal to
$$T = \frac{1}{f} \tag{4} \label{4}$$
Now the equation seems like what we know from classical mechanics, that speed is equal to distance (displacement) over time. Now, if you were to change the left-hand side (the speed of sound that is) you would have to change the right-hand side accordingly to keep the equation true.
Alas, you cannot abstractly change the values at will. We have to introduce some kind of constrain here. This is that the frequency of the sound cannot change (this means that the period must also stay constant). Then, the only quantity that can change is the wavelength. In order to find what is the necessary change to the wavelength for the equation to hold we could use equation (\ref{4}) with equation (\ref{2}) and get
$$ \lambda = c T \tag{5} \label{5}$$
This, of course, does not introduce new knowledge but allows to see what the difference to the wavelength should be. Period $T$ is constant (since it is related to the frequency which is constant), thus, as stated before, the constant of proportionality is the speed of sound $c$. If you double the speed, call the "previous" speed $c_{1}$, the "new" speed $c_{2} = 2 c_{1}$ and plug them in equation (\ref{5}) you get
$$ \lambda_{2} = c_{2} T \implies \lambda_{2} = 2 c_{1} T \implies \lambda_{2} = 2 \frac{c_{1}}{f} \implies \lambda_{2} = 2 \lambda_{1} $$
with $\lambda_{1}$ corresponding to the "previous" wavelength, valid for the "previous" speed.
Now, this is something that should make sense... Imagine a travelling (plane, for simplicity) monochromatic (single frequency) wave with frequency $f$. It completes a full period in $T$ seconds. If this wave travels with a specific speed, in the duration of $T$ seconds will cover distance $\lambda$. Now, if you increase (decrease) the speed it will cover a longer (shorter) distance in the same duration, which as already mentioned is invariant. Thus, its wavelength (which is the distance covered in one period time) will increase (decrease).