Semi-decidable problems with linear bound
For your sketched decision algorithm to work, it is sufficient that the run-time is majorized by a computable function. Every linear function $n \mapsto c\cdot n$ even for non-computable c is majorized by a computable function, viz., $n \mapsto \lceil c \rceil \cdot n$. Thus the answer to the question is no: a semi-decision procedure for an undecidable problem cannot have linear run-time (or a run-time majorized by any computable function.)