We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were for both directed and undirected graphs, and for undirected graphs with , where n is the number of nodes in the input graph. Our first algorithm has approximation ratio , which is except for very large values of k, namely, . This algorithm is based on a new result on -connected p-critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio for all values of . Combining these two gives an algorithm with approximation ratio , which asymptotically improves the best known approximation guarantee for directed graphs for all values of , and for undirected graphs for . Moreover, this is the first algorithm that has an approximation guarantee better than for all values of . Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation.