Side channel attack - execution time depends on the size of the key
Execution time of my algorithm/code depends on the size of the key. Is this a disqualifying problem?

No, because the key size is not considered a secret.
But having execution time depend on the bit size of the integer coded by the key would be something different. It would be a problem, more or less minor depending on the size we are talking about and algorithm/key generation method. For example, in RSA, that's typically not a serious issue for any of the integers defining the private key $p$, $q$, $d$, $d_p$, $d_q$, $q_\text{inv}$, because it's so unlikely that the bit size of these integers is significantly reduced compared to its maximum; and regarding $p$ and $q$, their bit size as an integer is customarily fixed to exactly half the bit size of $n=p\,q$.
What could be a serious side-channel issue would be that execution time depends on some secret data, like the key value, or plaintext in an encryption algorithm. The worse is when execution time depends on a combination of the key value and varying information known or under control of adversaries (e.g. key and ciphertext; or key and hash of signed data). That's ideal ground for a side-channel attack. That could well be the case if multiplication time depends on the value multiplied. That's a common and hard-to-avoid issue, see this.